import S0403SqQueue 

mg=[
    [1,1,1,1,1,1],
    [1,0,0,0,1,1],
    [1,0,1,0,0,1],
    [1,0,0,0,1,1],
    [1,1,0,0,0,1],
    [1,1,1,1,1,1],
]
# S0403SqQueue.test()

class Point:
    x=-1
    y=-1
    pre=None
    def __init__(self,x=-1,y=-1):
        self.x=x
        self.y=y

    def __str__(self):
        return "("+str(self.x)+","+str(self.y)+")"




def mgPath1(mg,queue,xi,yi,xe,ye):
    pointi=Point(xi,yi)
    queue.enQueue(pointi)
    mg[xi][yi]=-1
    find=False
    while(not queue.queueEmpty()) and (not find):
        data=queue.deQueue()
        print(data)
        if data.x==xe and data.y==ye:
            find=True
            return data
        for di in range(4):
            if di==0:
                x=data.x-1
                y=data.y
            elif di==1:
                x=data.x
                y=data.y+1
            elif di==2:
                x=data.x+1
                y=data.y
            elif di==3:
                x=data.x
                y=data.y-1
            if mg[x][y]==0:
                p=Point(x,y)
                p.pre=data
                queue.enQueue(p)
                mg[x][y]=-1
    return False

qu=S0403SqQueue.SqQueue()
qu.initQueue(100)
isFind=mgPath1(mg,qu,1,1,4,4)
print("结束了====================",isFind)
if isFind:
    data=isFind
    while data!=None:
        #print("(",data.x,",",data.y,")")
        print(data)
        data=data.pre
